package com.example.interview.algorithm;

/**
 * 
 * @Description: TODO
 * @author gaobing
 * @date 2018年9月27日 上午11:28:45
 * 题目二：不修改数组找出重复的数字
 * 在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，
 * 但不能修改输入的数组。例如：如果输入长度为8的数组{2，3，5，4，3，2，6，7}，那么对应的输出是重复的数字2或者3
 * 思路一：创建一个长度为n+1的辅助数组，按照数字与下标一致的原则，把原数组的数字复制到辅助数组。这样很容易发现哪个数字是重复的。
 * 思路二：二分查找,据悉性在于 不能判断某个数字出现一次或是出现2次 比如（1，2 和 1，1）
 */
public class Test03_2Duplicate {

	public static int getDuplicate(final int[] numbers) {
		if (numbers==null||numbers.length<=0) {
			return -1;
		}
		int start=1;
		int end=numbers.length-1;
		while(end>=start) {
			// <<      :     左移运算符，num << 1,相当于num乘以2
			// >>      :     右移运算符，num >> 1,相当于num除以2
			int middle=((end-start)>>1)+start;
			System.out.println("middle:"+middle);
			int count=countRange(numbers,numbers.length,start,middle);
			if (end==start) {
				if (count>1) {
					return start;
				}else{
					break;
				}
			}
			if (count>(middle-start+1)) {
				end=middle;
			}else {
				start=middle+1;
			}
		}
		return -1;
	}
	
	private static int countRange(int[] numbers, int length, int start, int end) {
		 if (numbers==null) {
			return 0;
		}
		 int count=0;
		 for(int i=0;i<length;i++) {
			 if (numbers[i]>=start&&numbers[i]<=end) {
				count++;
			}
		 }
		 return count;
	}

	public static void main(String[] args) {
//		int a=3/2;
//		System.out.println(a);
		int[] numbers=new int[]{2,3,3,4,1,4,6};
		int repeat=getDuplicate(numbers);
		System.out.println(repeat);
		
	}
}
